package club.xiaojiawei.array;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/20 22:39
 * @question 904.水果成篮
 * @description 你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
 * 你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
 * 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
 * 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
 * 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
 * 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
 */
public class FruitBaskets904 {

    public static void main(String[] args) {
        int[] fruits = {1,2,3,2,2};
        System.out.println("可收集的最多水果数："+totalFruit(fruits));
        System.out.println("可收集的最多水果数："+totalFruit1(fruits));
    }

    /**
     * 暴力解法 - 优化
     * @param fruits
     * @return
     */
    public static int totalFruit(int[] fruits) {
        int basket1 = -1, basket2 = -1;
        int amount = 0;
        int max = 0;
        for (int i = 0; i < fruits.length - max; i++) {
            for (int j = i; j < fruits.length; j++) {
                if (basket1 == -1){
                    basket1 = fruits[j];
                }else if (fruits[j] != basket1 && basket2 == -1){
                    basket2 = fruits[j];
                }else if (fruits[j] != basket1 && fruits[j] != basket2){
                    max = Math.max(max, amount);
                    break;
                }
                amount++;
            }
            max = Math.max(max, amount);
            amount = 0;
            basket1 = basket2 = -1;
            while (i + 1 < fruits.length && fruits[i + 1] == fruits[i]){
                i++;
            }
        }
        return max;
    }

    /**
     * 滑动窗口法
     * @param fruits
     * @return
     */
    public static int totalFruit1(int[] fruits) {
        if (fruits.length == 0){
            return 0;
        }
        int lastType = -1, currentType = fruits[0];
        int end = 0, start = 0, max = 0;
        while (end < fruits.length) {
            if (fruits[end] != currentType){
                if (lastType == -1){
                    lastType = fruits[end];
                }else if (lastType != fruits[end]){
                    max = Math.max(max, end - start);
                    start = end - 2;
                    while (start > -1 && fruits[start] == fruits[end - 1]){
                        start--;
                    }
                    lastType = fruits[++start];
                    currentType = fruits[end];
                }
            }
            end++;
        }
        return Math.max(max, end - start);
    }
}
